/*
 *https://leetcode.cn/problems/longest-palindromic-substring/
 *5. 最长回文子串
 *medium 吴朝泽 2024.10.11
 *区间DP
*/

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();  // 获取字符串的长度
        vector<vector<bool>> dp(n, vector<bool>(n, true));   // 用于记录子串是否是回文
        int k = 0;  // 记录最长回文子串的起始索引
        int mx = 1;  // 记录最长回文子串的长度

        // 从字符串的倒数第二个字符开始，向前遍历
        for (int i = n - 2; ~i; --i) 
        {
            // 遍历 i 后面的每个字符 j
            for (int j = i + 1; j < n; ++j) 
            {
                dp[i][j] = false; 
                // 如果字符相同，则可能是回文
                if (s[i] == s[j]) 
                {
                    // 检查 i+1 到 j-1 的子串是否是回文
                    dp[i][j] = dp[i + 1][j - 1];
                    // 如果 dp[i][j] 为 true，且当前回文长度大于 mx
                    if (dp[i][j] && mx < j - i + 1) 
                    {
                        mx = j - i + 1; // 更新最长回文长度
                        k = i;          // 更新起始索引
                    }
                }
            }
        }
        return s.substr(k, mx);
    }
};
